package SegmentTree;

//线段树 实现
//增加 改 查
// 使用数组实现int 型线段树 且是找出最小值
public class SegmentTree {

    private int size;
    private Node[] data;

    public SegmentTree(int []arr)
    {
        this.size=arr.length;
        data=new Node[size*4];
        buildTree(arr,0,size-1,0);
    }

    //添加
    public void buildTree(int []arr,int left,int right,int index)
    {
        if(left==right)
        {
            data[index]=new Node(left,right,arr[left]);
            return ;
        }
        int mid=(left+right)/2;
        int leftIndex=2*index+1;
        int rightIndex=2*index+2;
        buildTree(arr,left,mid,leftIndex);
        buildTree(arr,mid+1,right,rightIndex);
        Node root=new Node(left,right);
        root.value=data[leftIndex].value<data[rightIndex].value?data[leftIndex].value:data[rightIndex].value;
        data[index]=root;
    }

    //查找
    public int search(int index,int left,int right)
    {
        if(left==data[index].left&&right==data[index].right)
        {
            return data[index].value;
        }
        int mid=(data[index].left+data[index].right)/2;
        if(mid<left)
        {
            return search(index*2+2,left,right);
        }
        else if(right<=mid)
        {
            return search(index*2+1,left,right);
        }

        int l=search(index*2+1,left,mid);
        int r=search(index*2+2,mid+1,right);
        return l<r?l:r;
    }

    //更新
    public void update(int index,int tar,int value)
    {
        if(data[index].left==data[index].right&&tar==data[index].left)
        {
            data[index].value=value;
            return;
        }
        int mid=(data[index].left+data[index].right)/2;
        if(tar>mid)
        {
            update(index*2+2,tar,value);
        }
        else if(tar<=mid)
        {
            update(index*2+1,tar,value);
        }
        data[index].value=data[index*2+1].value<data[index*2+2].value?data[index*2+1].value:data[index*2+2].value;
    }


    private class Node
    {
        public int left;
        public int right;
        public int value;
        public Node(int left,int right,int value)
        {
            this.left=left;
            this.right=right;
            this.value=value;
        }

        public Node(int left,int right)
        {
            this.left=left;
            this.right=right;
        }
    }
}
